Recursion is a programming technique in which a method calls itself repeatedly until a base condition is met.

Main components of recursion:

• Base case - Stops the recursion to prevent an infinite loop.
• Recursive case - The function calls itself with modified parameters.

 

Types of Recursion

1. Direct recursion - a method calls itself directly.
2. Indirect recursion - a method calls another method, which then calls the original method.
3. Tail recursion - the recursive call is the last statement in the function.
4. Head recursion - the recursive call occurs before any computation.
5. Tree recursion - a function makes multiple recursive calls.
6. Nested recursion - the argument to a recursive function is itself a recursive call.

 

1. Direct Recursion

Let's calculate the factorial of a number using Direct recursion:

class RecursionExample {
   static int factorial(int n) {
       if (n == 0 || n == 1)  // Base Case
           return 1;
       return n * factorial(n - 1); // Recursive Case
   }
   public static void main(String[] args) {
       System.out.println("Factorial of 6: " + factorial(6)); 
   }
}

Output

Factorial of 6: 720

 

2. Indirect Recursion

In indirect recursion, two or more functions call each other.

class IndirectRecursion {
   static void methodA(int n) {
       if (n > 0) {
           System.out.print(n + " ");
           methodB(n - 1);
       }
   }
   static void methodB(int n) {
       if (n > 0) {
           System.out.print(n + " ");
           methodA(n / 2);
       }
   }
   public static void main(String[] args) {
       methodA(10);
   }
}

Output

10 9 4 3 1 

 

3. Tail Recursion

In tail recursion, the recursive call is the last operation in the function.

class TailRecursionExample {
   static void printNumbers(int n) {
       if (n == 0) return; // Base Case
       System.out.println(n);
       printNumbers(n - 1); // Tail Recursion
   }
   public static void main(String[] args) {
       printNumbers(5);
   }
}

Optimized for performance, as there is no additional computation after the recursive call.

Output

5
4
3
2
1

 

4. Head Recursion

In head recursion, the recursive call is made before any computation is performed.

class HeadRecursionExample {
   static void printNumbers(int n) {
       if (n == 0) return; // Base Case
       printNumbers(n - 1); // Head Recursion
       System.out.println(n);
   }
   public static void main(String[] args) {
       printNumbers(5);
   }
}

 

Output

1
2
3
4
5

4. Tree Recursion

In tree recursion, a function calls itself multiple times.

class TreeRecursionExample {
   static void treeRec(int n) {
       if (n == 0) return;
       System.out.println(n);
       treeRec(n - 1);
       treeRec(n - 1);
   }
   public static void main(String[] args) {
       treeRec(3);
   }
}

Output

3
2
1
1
2
1
1

 

5. Nested Recursion

In nested recursion, the argument of the function is itself a recursive call.

class NestedRecursionExample {
    static int nestedRec(int n) {
        if (n > 100) return n - 10;
        return nestedRec(nestedRec(n + 11));
    }

    public static void main(String[] args) {
        System.out.println(nestedRec(95));
    }
 }

Nested recursion is rare but useful in complex mathematical calculations.

Output

91

 

Recursion vs. Iteration

Feature	Recursion	Iteration
Definition	Function calls itself	Uses loops (for, while)
Memory Usage	Uses more memory (stack frames)	Uses less memory
Speed	Can be slower (due to stack overhead)	Faster in many cases
Complexity	Simpler for problems like tree traversal	More efficient in loops
Example	Fibonacci, Factorial, Tower of Hanoi	Printing numbers, summation

 

When to use recursion?

• When the problem is naturally broken down into smaller sub-problems.
• In tree structures, graphs, and divide-and-conquer algorithms.
• When code readability is more important than performance.

 

Also, read: Pass by Value vs. Pass by Reference in Java